package com.cloud.basic.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @program: basic
 * @description: 通过栈实现对根节点下的所有叶节点的遍历
 * @author: Cloud
 * @create: 2020/12/7 14:45:44
 */
public class Traversal {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode("1");
        TreeNode treeNode2 = new TreeNode("2");
        TreeNode treeNode3 = new TreeNode("3");
        TreeNode treeNode4 = new TreeNode("4");
        TreeNode treeNode5 = new TreeNode("5");
        TreeNode treeNode6 = new TreeNode("6");

        treeNode1.addChildren(treeNode2,treeNode3);
        treeNode2.addChildren(treeNode4,treeNode5);
        treeNode5.addChildren(treeNode6);

        List<TreeNode> leafs = traversalByStack(treeNode1);
        for (TreeNode leaf : leafs) {
            System.out.println("leaf = " + leaf.getData());
        }
    }

    public static List<TreeNode> traversalByStack(TreeNode root){
        List<TreeNode> nodes = new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 将根元素推入到栈中
        stack.push(root);
        while (!stack.isEmpty()) {
            // 去除栈顶中的元素，并从栈里删除
            TreeNode node = stack.pop();
            // 如果是叶节点
            if (node.isLeaf()) {
                nodes.add(node);
            } else {
                // 取非叶节点的所有子节点
                List<TreeNode> children = node.getChildren();
                // 将所有子节点加入栈
                stack.addAll(children);
            }
        }
        return nodes;
    }


    static class TreeNode {
        private List<TreeNode> children;
        private String data;

        public TreeNode(String data){
            this.data = data;
        }

        public void addChildren(TreeNode... child){
            if (child != null && child.length < 1) {
                return;
            }
            if (children == null) {
                children = new ArrayList<TreeNode>();
            }
            children.addAll(Arrays.asList(child));
        }

        public List<TreeNode> getChildren() {
            return children;
        }

        public void setChildren(List<TreeNode> children) {
            this.children = children;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

        public boolean isLeaf(){
            return children == null || children.isEmpty();
        }
    }
}
